The present invention relates to a video format conversion system, and in particular to a video format conversion system for converting interlaced video into progressive video.
Video displays generally have a plurality of scan lines that are displayed at regular intervals. Traditional displays, such as those used in regular television displays, have used interlaced scan displays. Interlaced systems divide the scan lines of each frame of video into two fields, each of which consists of one half (every other line) of the total number of scan lines in the frame. The resolution of interlaced scan displays is limited because each field is separately displayed with the lines of the alternate field being black. In the NTSC system, each interlaced field is displayed every 1/60th of a second and a complete frame is displayed every 1/30th of a second (two fields).
Higher quality displays, such as high definition television, use a progressive scan display system. In a simple progressive scan display system, the number of scan lines visible at a given instant is twice that which is visible in a corresponding interlaced system. Progressive video means that every line of the image signal is successively displayed instead of every other line as contemplated by the term interlaced video. In other words, the term progressive video means not interlaced video.
The conversion from interlaced video to progressive video may be accomplished by scanning the interlaced video at twice the horizontal rate to double the number of scan lines of video information. Each line of interlaced video of a field is displayed and the missing lines (that would normally be black) between the lines of the interlaced video are interpolated.
Many systems for interpolating video pixel information of interlaced video to progressive video are known. Such systems can be broadly categorized into one of three types.
The first interpolation system is intra-field interpolation which involves interpolating the pixels of lines not scanned by using the pixels of scanned lines only in the current field. Normally such systems result in a deterioration of image quality because each line is interpolated in some manner by the mean value of pixels on directly adjacent upper and lower lines with respect to the line being interpolated. The simplest intra-field system averages the value of the pixel immediately above and the value of the pixel immediately below the interpolated pixel to obtain an average pixel value. While filling the black regions between interlaced lines of video, this particular intra-field method neither provides for sufficient image quality nor eliminates flicker associated with small details.
The second interpolation system is inter-field interpolation which involves interpolating lines not scanned during the current field by using scanned lines of the current field together with scanned lines of past and/or future fields, without any motion compensation. Although this method may result in high image quality for video with stationary scenes, severe artifacts arise for video portions that involve motion. An alternative inter-field interpolation method stores one field and uses it to fill the spaces in the following field. This approach is satisfactory except for video portions that involve motion because a moving object will be at different locations in adjacent fields. In other words, such an interpolated frame, consisting of two superimposed fields, will present a moving object at one location on even lines and at another location on odd lines, thus producing a double image of the object.
The third interpolation system is interpolation with motion compensation which attempts to solve the problems encountered with the presence of motion associated with the intra-field interpolation method and the inter-field interpolation method without motion compensation. However, motion compensation normally requires substantially more computation, at increased time and expense. Many interpolation systems try to compensate for the presence of motion by sampling pixel values in an area around the desired pixel and extending the sampling of pixels to past and future fields in the region of the desired interpolated pixel. Difficulties of motion compensation for interlaced video include compensating for the sampling of pixels that are not in the same spatial location in the immediately prior and immediately subsequent fields of the field including the interpolated pixel. Also, in the event of a scene change, i.e., an event involving a substantial amount of video change, such systems tend to fail.
Lee et al., U.S. Pat. No. 5,428,397, disclose a video format conversion system for converting interlaced video into progressive video using motion-compensation. The Lee et al. system uses both an intra-field technique and an inter-field technique to achieve the conversion. The system determines if the current pixel is stationary, and if so then an inter-field technique is used to determine the value of the interpolated pixel. In contrast, if the system determines that the current pixel is in motion, then an intra-field motion compensating technique is used to determine the value of the interpolated pixel. In particular, the intra-field technique taught by Lee et al. uses a simple mean calculating circuit connected to a pair of line delay circuits. Accordingly, the relatively fast inter-field technique is used on the non-motion portions and the relatively slow intra-field technique is used on the motion portions for which the relatively fast inter-field technique is not suitable.
Bretl, U.S. Pat. No. 5,475,438, discloses a pixel interpolation system for developing progressive line scan video from two interlaced fields of video, using both an intra-field technique and an inter-field technique. An intra-field pixel value is determined by averaging the pixel in the line above and the pixel in the line below the desired pixel. A motion value is determined indicative of motion of the image. An inter-field pixel value is determined by comparing the intra-field pixel value with the corresponding pixels in the previous and subsequent frames. The motion value is used to proportion the intra-field and the inter-field pixel values to compute a value for the desired pixel. The system taught by Bretl is computationally complex, thus requiring expensive electronics and excessive time to compute.
Simonetti et al., in a paper entitled A DEINTERLACER FOR IQTV RECEIVERS AND MULTIMEDIA APPLICATIONS, disclose a system for converting interlaced video to progressive scan video. Simonetti et al. suggest that their objective is to improve picture quality with a fast, low-cost device by using simple but effective algorithms with an optimized design flow and silicon technology suitable for ASIC developments. The system includes motion detection by computing the absolute differences between selected pixels, and thereafter selecting either an intra-field or inter-field interpolation technique. When motion is detected, an intra-field technique is used to attempt to avoid smearing the borders of objects in the proximity of the pixel. Simonetti at al. attempt to keep the blurring low by performing an interpolation along a direction of high correlation of the luminance data in the vicinity of the pixel. The algorithm taught by Simonetti et al. includes performing an extensive number of comparisons (conditional executions) for each pixel and then selecting the proper action based upon one or more of the comparisons. Unfortunately, in conventional RISC processors conditional executions, which are used to perform such comparison operations, require substantial time to execute. Accordingly, to maximize computational speed when using a RISC processor, the number of conditional executions should be minimized.
Hong, U.S. Pat. No. 5,493,338, discloses a system for converting interlaced video to progressive video by utilizing a three dimensional median filter. The three dimensional median filter applies a weighing factor to pixel components of horizontal, vertical, and diagonal directions of the pixel component's periphery to be interpolated by horizontal, vertical, and time axis judging signals. However, Hong utilizes a large set of rules to determine the desired luminescence of the interpolated pixel which is inefficient for RISC processors. Further, Hong does not use edges in the video when determining pixel interpolation which may result in decreased image quality.
Marsi et al., in a paper entitled VLSI IMPLEMENTATION OF A NONLINEAR IMAGE INTERPOLATION FILTER, disclose the conversion of interlaced video to progressive video by interpolating along either the vertical or the horizontal direction using an operator function. The operator function is designed to preserve edges within an image. However, such an operator function does not account for image movement or provide adequate results for non-horizontally or non-vertically oriented edges.
Dong-Il, U.S. Pat. No. 5,307,164, discloses a system for conversion of interlaced video to progressive video by linearly interpolating through a slant correlation of a low-pass interpolation signal and through "0" insertion of a high-pass interpolation signal in a vertical direction. The slant correlation technique involves obtaining the mean value of highly correlated pixels, wherein the correlation of the pixels is detected in diagonal directions and vertical directions by a series of calculations. Thereafter, the greatest correlation (smallest mean value) is determined by a series of comparisons and used to select which two pixels to average in order to calculate the interpolated pixel. However, Dong-Il utilizes a large set of rules involving comparisons to determine the luminescence of the interpolated pixel which is computationally expensive using RISC processors.
Patti et al., U.S. Pat. No. 5,602,654, disclose a two-step, contour sensitive deinterlacing system especially suitable for obtaining still images from interlaced video. The first step determines for each missing pixel of an interlaced field whether the absolute difference between the pixels above and below the missing pixel is greater than a preselected threshold value. If it is decided that the missing pixel lies at a low-vertical frequency location, its value is estimated via vertical interpolation. Otherwise, the second step determines whether or not there is a well-defined contour passing through the missing pixel, and to determine its direction if there is one by comparing blocks of pixels. In the presence of a well defined contour, the missing pixel is obtained by averaging the intensity values along the direction of the contour in the field lines immediately above and below the missing field line. However, the computational requirements necessary to process the blocks of data, as taught by Patti et al., to determine the contours are excessive. In addition, the large set of conditional executions required to determine the contours are time consuming using RISC processors.
Martinez et al., in a paper entitled SPATIAL INTERPOLATION OF INTERLACED TELEVISION PICTURES, teach a system for converting interlaced video to progressive video by an algorithm that attempts to determine edges of features within an image by using corresponding sets of pixels of two adjacent lines of interlaced video. The algorithm is based on a line shift model, in which small segments of adjacent raster scan lines are assumed to be related by a spatially varying horizontal shift. The algorithm taught by Martinez et al. involves two steps. The first step is to estimate of the velocity obtained from a window of image samples surrounding the point of interest. For color pictures, this operation is carried out only on the luminance component. In order to compute the velocity estimate Martinez et al. teaches that a set of linear equations must be solved for each point, which is computationally intensive and potentially requires expensive electronics. The second step involves projecting the velocity estimate onto the two lines adjacent to the desired interpolated pixel and the image intensities at the corresponding points are averaged together. For color pictures, this operation takes place on each component color.
Conceptually the algorithm taught by Martinez et al. can be thought of as fitting a surface to a series of points on two adjacent interlaced lines of video. Then at the point of interest the gradient is determined, which is the direction of the steepest slope on the surface to that point of interest. The perpendicular to that gradient is the flattest portion at that point on the surface and is considered an edge to a feature. The interpolation is performed with pixels generally along that perpendicular to maintain the contour of the edge. Accordingly, Martinez et al. teach that pixel values from both lines are used to compute the interpolated line of pixels. Further, when proceeding to the next set of two lines of interlaced video, one line of which was used for the interpolation of the preceding interpolated line, there is no reusable data to simplify the calculations because of the "surface" nature of the calculations.
What is desired, therefore, is a system for converting interlaced video to progressive video that is not computationally inventive and results in retaining edge information for features within the video.